class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> v={""};
        map<char,string> m={{'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},
                            {'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};
        if(digits.empty())
        {
            v.erase(v.begin());
            return v;
        }
        for(int i=0;i<digits.size();i++)
        {
            char ch=digits[i];
            string tmp;
            int n=v.size();
            for(int j=0;j<n;j++)
            {
                tmp=v[0];
                v.erase(v.begin());
                for(char k:m[ch])
                {
                    v.push_back(tmp+k);
                }
            }
        }
        return v;
    }
};

class Solution {
public:
    vector<string> ret;
    string path;
    unordered_map<char, string> hash = {
        {'2', "abc"}, {'3', "def"},  {'4', "ghi"}, {'5', "jkl"},
        {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0)return vector<string>();
        dfs(digits, 0);
        return ret;
    }

    void dfs(string digits, int pos) {
        if (pos == digits.size()) {
            ret.push_back(path);
            return;
        }

        char num = digits[pos];
        for (auto e : hash[num]) {
            path.push_back(e);
            dfs(digits, pos + 1);
            path.pop_back();
        }
    }
};